/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class ShortestCompletingWord {
	int validLen = 0;

	public String shortestCompletingWord(String licensePlate, String[] words) {
		int[] freqL = getFreq(licensePlate);
		int vL = validLen;
		int minLen = Integer.MAX_VALUE;
		String reString = null;
		for (String string : words) {
			if (string.length() < vL) {
				continue;
			}
			int[] f = getFreq(string);
			if (greaterOrEqual(f, freqL)) {
				if (string.length() < minLen) {
					reString = string;
					minLen = string.length();
				}
			}
		}
		return reString;
	}

	private boolean greaterOrEqual(int[] f, int[] freqL) {
		for (int i = 0; i < freqL.length; i++) {
			if (f[i] < freqL[i]) {
				return false;
			}
		}
		return true;
	}

	private int[] getFreq(String licensePlate) {
		int[] freqL = new int[26];
		for (int i = 0; i < licensePlate.length(); i++) {
			char ch = licensePlate.charAt(i);
			if ('A' <= ch && ch <= 'Z') {
				freqL[ch - 'A']++;
				validLen++;
			} else if ('a' <= ch && ch <= 'z') {
				freqL[ch - 'a']++;
				validLen++;
			}
		}
		return freqL;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words = { "looks", "pest", "stew", "show" };
		String licensePlate = "1s3 413";
		System.out.println(new ShortestCompletingWord().shortestCompletingWord(licensePlate, words));
	}

}
